This invention relates generally to branch prediction, and more specifically, to state machine-based filtering in pattern history tables.
In computer architecture, a branch predictor is the part of a processor that determines whether or not a conditional branch in an instruction flow of a program is likely to be taken. Branch predictors allow processors to fetch and execute instructions without waiting for a branch to be resolved. One type of branch predictor is a bimodal predictor that utilizes a branch history table (BHT) of two-bit entries and is indexed with part or all of the instruction addresses. The bimodal predictor provides high accuracy on most branches, particularly those that are dominant. Dominant branches refer to those that often exhibit the same direction (i.e., taken/not taken). However, the bimodal predictor is known to be much less accurate in predicting non-dominant branches (which do not reliably exhibit the same direction) as compared with dominant branches.
Pattern-based prediction algorithms provide high accuracy for non-dominant branches but can be costly to implement in terms of chip area coverage and power consumption requirements. A branch predictor using a pattern history table (PHT) is based on paths leading up to the given branch. By basing the prediction value on the path that was taken to get to the given branch, the directionally guessed path is no longer based on the general occurrence for a given branch, but rather a path of previous taken and not taken branches leading to the given branch. Such paths can be global paths where the path of the last ‘n’ number of branches is used to determine the guess of the current branch. The histories of branches' outcomes for encountered paths are stored in the pattern history table.
Hybrid branch prediction schemes have been developed that take advantage of the strengths of different predictors. For example, state machine-based filtering, uses a pattern-based predictor (e.g., share) only on non-dominant branches, which allows the predictor to be implemented with a much smaller pattern history table (PHT) than would otherwise be possible if dominant branches were included. The prediction state associated with each branch is updated according to a state machine that attempts to recognize those branches that would benefit from the PHT.
The PHT is indexed as a function of the outcomes (taken vs. not-taken) of previous branches. A fixed number of such previous branch outcomes are used. In some cases, different outcomes of the same branch will have the same PHT index. Oftentimes this is due to limited history length. In such cases, the PHT is not able to effectively correlate the pattern history with the branch's outcome and it is disadvantageous to use the PHT for such branches, particularly in a hybrid configuration where that PHT resource could be more effectively used to predict another branch.